package com.zdp.leetcodeMiddle;


/*
* 题目描述：
* 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例 1：
输入：matrix = [['1','0','1','0','0'],['1','0','1','1','1'],['1','1','1','1','1'],['1','0','0','1','0']]
输出：4
示例 2：
输入：matrix = [['0','1'],['1','0']]
输出：1
示例 3：
输入：matrix = [['0']]
输出：0
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 最大正方形_221 {
    public static void main(String[] args) {
        最大正方形_221 demo = new 最大正方形_221();
        char[][] matrix = new char[][] {
                {'1','0','1','0','0'}
                ,{'1','0','1','1','1'}
                ,{'1','1','1','1','1'}
                ,{'1','0','0','1','0'}
        };
        int i = demo.maximalSquare(matrix);
        System.out.println(i);
    }

    /*
    * 解题思路： dp[i][j] 表示以(i,j)为右下角，且只包含1的最大正方形边长
    * 根据 给的例子 可以推出 状态转移方程
    *  dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]) +1
    * */
    public int maximalSquare(char[][] matrix) {
        int[][] dp = new int[matrix.length][matrix[0].length];
        int max = 0;

        for(int i= 0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length ;j ++){
                if(matrix[i][j] == '1'){
                    // 处理第一行和第一列
                    if(i==0 || j==0){
                        dp[i][j] = 1;
                    }else{
                        // 计算dp
                        // 找最小
                        int min = Math.min(dp[i-1][j-1],dp[i][j-1]);
                        min = Math.min(min,dp[i-1][j]);
                        dp[i][j] = min+1;
                    }
                    max = Math.max(max,dp[i][j]);
                }
            }
        }
        return max*max;
    }

    /*
    * 暴力解法： 遍历到的那个i,j作为左上角，然后计算 以该点为左上角的最大正方形边长
    * */
    public int maximalSquare1(char[][] matrix) {
        int maxSide = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide;
        }
        int rows = matrix.length, columns = matrix[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    // 遇到一个 1 作为正方形的左上角
                    maxSide = Math.max(maxSide, 1);
                    // 计算可能的最大正方形边长
                    int currentMaxSide = Math.min(rows - i, columns - j);
                    for (int k = 1; k < currentMaxSide; k++) {
                        // 判断新增的一行一列是否均为 1
                        boolean flag = true;
                        if (matrix[i + k][j + k] == '0') {
                            break;
                        }
                        for (int m = 0; m < k; m++) {
                            if (matrix[i + k][j + m] == '0' || matrix[i + m][j + k] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        if (flag) {
                            maxSide = Math.max(maxSide, k + 1);
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }
}
